package huawei.year2016;

import java.util.Scanner;

/**
 * Created by Hyman on 2017/3/16.
 * <p>
 * 数独是一个我们都非常熟悉的经典游戏，运用计算机我们可以很快地解开数独难题，现在有一些简单的数独题目，请编写一个程序求解。
 * 这里的数独就是9行9列的数组，满足每一行、每一列、每一个3*3粗线宫内的数字均含1-9，不重复。
 * <p>
 * 输入描述: 输入9行，每行为空格隔开的9个数字，为0的地方就是需要填充的。
 * 输出描述: 输出九行，每行九个空格隔开的数字，为解出的答案
 */
public class Sudoku2 {


    public static void main(String[] args) {

        //Scanner scanner = new Scanner(System.in);
        Scanner scanner = new Scanner(Sudoku2.class.getClassLoader().getResourceAsStream("huawei/year2016/data.txt"));

        while (scanner.hasNext()) {

            int[][] sudoku = new int[9][9];

            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sudoku[i][j] = scanner.nextInt();
                }
            }

            solveSudoku(sudoku, 0);

            System.out.println(ArrToString(sudoku));
        }

        scanner.close();
    }

    private static boolean solveSudoku(int[][] sudoku, int index) {

        if (index == 81) {
            return true;
        }

        int m = index / 9;
        int n = index % 9;

        if (sudoku[m][n] != 0) {
            return solveSudoku(sudoku, index + 1);
        } else {

            for (int i = 1; i <= 9; i++) {
                if (checkRows(sudoku, m, n, i) && checkCols(sudoku, m, n, i) && checkBlocks(sudoku, m, n, i)) {

                    sudoku[m][n] = i;

                    if (solveSudoku(sudoku, index + 1)) {
                        return true;
                    } else {
                        sudoku[m][n] = 0;
                    }
                }
            }
            return false;

        }
    }

    private static boolean checkRows(int[][] sudoku, int row, int col, int num) {
        for (int i = 0; i < 9; i++) {
            if (col != i && sudoku[row][i] == num) {
                return false;
            }
        }
        return true;
    }

    private static boolean checkCols(int[][] sudoku, int row, int col, int num) {
        for (int i = 0; i < 9; i++) {
            if (row != i && sudoku[i][col] == num) {
                return false;
            }
        }
        return true;
    }

    private static boolean checkBlocks(int[][] sudoku, int row, int col, int num) {
        for (int i = row / 3 * 3; i < (row / 3 + 1); i++) {
            for (int j = col / 3 * 3; j < (col / 3 + 1); j++) {
                if(i != row && j!= col && sudoku[i][j] == num) {
                    return false;
                }
            }
        }
        return true;
    }


    private static String ArrToString(int[][] sudoku) {

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                sb.append(sudoku[i][j] + " ");
            }
            sb.setCharAt(sb.length() - 1, '\n');
        }
        return sb.substring(0, sb.length() - 1);
    }
}
